import collections
class Solution(object):
    def numberOfGoodSubsets(self, nums):
        zhishu = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        zhishu_dict = {num: index for index, num in enumerate(zhishu)}
        p = [0] * 31
        for i in range(2, 31):
            num = i
            val = -1
            for d in zhishu:
                if num % d == 0:
                    last_num = num // d
                    if (p[last_num] >> zhishu_dict[d]) & 1 == 0:
                        val = p[last_num] | (1 << zhishu_dict[d])
                    break
            p[i] = val 
        base = 10 ** 9 + 7
        c = collections.Counter(nums)
        now_dict = {0: 1}
        ans = -1
        for num in range(2, 31):
            if p[num] >= 0:
                next_dict = collections.defaultdict(int)
                for val in now_dict:
                    next_dict[val] += now_dict[val]
                    if p[num] & val == 0:
                        next_dict[val | p[num]] += now_dict[val] * c[num]
                        next_dict[val | p[num]] %= base
                now_dict = next_dict
        t = 2 ** c[1]
        for val in now_dict:
            ans = (ans + now_dict[val]) % base
        ans = ans * t % base
        return ans 
                    

                 
data = Solution()
nums = [4,2,3,15]
nums = [1,2,3,4,2,3,6,10,8,2,9,15,1]
print(data.numberOfGoodSubsets(nums))
